/*
    爬楼梯
    假设你正在爬楼梯，需要n阶才能到达楼顶。
    每次你可以爬1或2个台阶，你有多少种不同的方法可以爬到楼顶
    注意：给定n是一个正整数
*/

#include <stdio.h>

// int climbStairs(int n)   //普通递归法，时间复杂度高，超时
// {
//     if(0==n)    return 0;

//     if(1==n)
//         return 1;
//     if(2==n)
//         return 2;
    
//     return climbStairs(n-1)+climbStairs(n-2);
// }

long long int climbStairs(int n)  
{
    long long int p=0,q=0,r=1;
    for(int i=1;i<=n;i++)
    {
        p = q;
        q = r;
        r = p+q;
    }
    return r;
}

int main(int argc, char const *argv[])
{
    int n=0;

    while(1)
    {
        printf("请输入有多少级台阶：");
        scanf("%d",&n);

        printf("有%lld种方法\n",climbStairs(n));
    }

    return 0;
}

